package leetcode.editor.cn;//给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
//
// 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
//
//
//
// 示例 1:
//
//
//输入: [3,2,1,5,6,4] 和 k = 2
//输出: 5
//
//
// 示例 2:
//
//
//输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
//输出: 4
//
//
//
// 提示：
//
//
// 1 <= k <= nums.length <= 104
// -104 <= nums[i] <= 104
//
// Related Topics 数组 分治 快速选择 排序 堆（优先队列）
// 👍 1410 👎 0


//leetcode submit region begin(Prohibit modification and deletion)

class Solution215 {
    public int findKthLargest(int[] nums, int k) {
        //quickSort(nums, 0, nums.length - 1, k);
        heapSort(nums,k);
        return nums[nums.length-k];
    }
    public void heapSort(int[] nums,int k){
        int len=nums.length;
        buildMaxHeap(nums,len);
        //堆排序每次都可以选出一个最大值放到其最终位置
        int tmp;
        for(int i=0;i<nums.length;i++){
            //每轮排序把当前待排序列中的最大值放到最终位置
            tmp=nums[0];//nums[0]和nums[len-1-i]交换
            nums[0]=nums[len-1-i];
            nums[len-1-i]=tmp;
            //所以针对这道题，k次交换即可得到结果
            if(i==k-1) break;
            adjustMaxHeap(nums,0,len-1-i);
        }

    }
    //从最后一个非叶节点开始调整，数组长度为len
    public void buildMaxHeap(int[] nums,int len){
        for (int i = nums.length/2-1; i >=0 ; i--) {
            adjustMaxHeap(nums,i,len);
        }
    }
    //调整以nums[root]为根的树为最大堆，调整范围为nums[root,len-1]
    public void adjustMaxHeap(int[] nums,int root,int len){
        int rootVal=nums[root];
        //比较root和其子结点，看其是否符合最大堆定义
        //r的左孩子下标为2r+1
        for(int i=2*root+1;i<len;i=2*i+1){
            //i指向值最大的子结点
            if(i+1<len&&nums[i]<nums[i+1]) i++;
            //符合大根堆，结束遍历
            if(nums[i]<rootVal) break;
            //将较大值放到root
            nums[root]=nums[i];
            //root最终指向rootVal存放的位置
            root=i;
        }
        nums[root]=rootVal;
    }

    //快排
    public void quickSort(int[] nums, int l, int r, int k) {
        if (l >= r) return;
        int pivot;
        //第k大元素下标为k-1

        pivot = partition(nums, l, r);
        if (pivot == k - 1) ;
        else if (pivot > k - 1)
            quickSort(nums, l, pivot - 1, k);
        else
            quickSort(nums, pivot + 1, r, k);

        return;
    }
    //逆序
    public int partition(int[] nums, int l, int r) {
        int pivot = nums[l];
        while (l < r) {
            while (l < r && nums[r] >= pivot) r--;
            nums[l] = nums[r];
            while (l < r && nums[l] <= pivot) l++;
            nums[r] = nums[l];
        }
        nums[l] = pivot;
        return l;
    }

}
//leetcode submit region end(Prohibit modification and deletion)
